package 剑指offer.双指针法;

import java.util.Arrays;

/**
 * 调整数组里面的元素的顺序，把奇数放到前面，偶数放到后面
 */
public class 第21题调整数组顺序使奇数位于偶数前面 {

    /*
    一下就能想到的办法一般不是面试官想要的，如：遍历交换，他的时间复杂度是 O(n^2)

    双指针法：
    头指针找偶数、尾指针找奇数
    找到了就交换位置，直到两个指针相遇或者错位
     */
    public static void reOrderArray(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        int i = 0;
        int j = array.length - 1;
        while (i < j) {
            // 头指针找偶数
            while (i < j && (array[i] & 1) != 0) {
                // 调整因为数据交换而导致的顺序混乱问题，升序排列
                if (i > 0 && array[i] < array[i - 1]) {
                    array[i] ^= array[i - 1];
                    array[i - 1] ^= array[i];
                    array[i] ^= array[i - 1];
                }
                i++;
            }
            // 尾指针找到奇数
            while (i < j && (array[j] & 1) == 0) {
                if (j < array.length - 1 && array[j] > array[j + 1]) {
                    array[j] ^= array[j + 1];
                    array[j + 1] ^= array[j];
                    array[j] ^= array[j + 1];
                }
                j--;
            }
            if (i < j) {
                array[i] ^= array[j];
                array[j] ^= array[i];
                array[i] ^= array[j];
            }
        }
        if (j < array.length - 1 && array[j] > array[j + 1]) {
            array[j] ^= array[j + 1];
            array[j + 1] ^= array[j];
            array[j] ^= array[j + 1];
        }

        System.out.println(Arrays.toString(array));
    }


    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8};
        reOrderArray(array);
    }
}
